package com.myc.subjects.stackandqueue;

import com.myc.subjects.utils.ArrayUtils;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * LeetCode题号：84
 *
 * 柱状图中最大的矩形
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 * 示例 2：
 * 输入： heights = [2,4]
 * 输出： 4
 *
 * 提示：
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Zhuzhuangtuzhongzuidadejuxing {

    public static void main(String[] args) {
        int[] heights = new int[]{2,1,5,6,2,3};
        //int[] heights = new int[]{1,1};
        Zhuzhuangtuzhongzuidadejuxing zhuzhuangtuzhongzuidadejuxing = new Zhuzhuangtuzhongzuidadejuxing();
        System.out.println(zhuzhuangtuzhongzuidadejuxing.largestRectangleArea5(heights));
    }

    /**
     * 方法一：暴力法（固定底边）
     * 时间复杂度：O(n^2)
     * 枚举所有可能的底边，再乘以高度，找出最大的面积
     */
    public int largestRectangleArea1(int[] heights) {
        int maxArea = 0;//定义最大面积
        for(int i = 0; i < heights.length; i++){
            int minHeight = heights[i];//定义最小高度
            for(int j = i; j < heights.length; j++){
                minHeight = heights[j] < minHeight ? heights[j] : minHeight;//找出范围内最小的高度
                int area = (j - i + 1) * minHeight;//面积等于最小的高度乘以底边宽度
                maxArea = area > maxArea ? area : maxArea;//比较得出更大的面积
            }
        }
        return maxArea;
    }

    /**
     * 方法二：双指针（固定高度）
     * 时间复杂度：O(n^2)
     * 定义两个指针，固定一个基准高度，分别向左右找到比他低的高度即停止。此时的宽度乘以基准高度即当前高度的最大面积
     */
    public int largestRectangleArea2(int[] heights) {

        int maxArea = 0;//定义最大面积

        for(int i = 0; i < heights.length; i++){
            //左右指针都从i开始
            int left = i;
            int right = i;

            //左指针向左遍历，找到更小的高度停止
            while(left >= 0){
                if(heights[left] < heights[i]) break;
                left--;
            }
            //右指针向右遍历，找到更小的高度停止
            while(right < heights.length){
                if(heights[right] < heights[i]) break;
                right++;
            }
            //面积等于宽度乘以基准高度
            int area = (right - left - 1) * heights[i];
            maxArea = area > maxArea ? area : maxArea;
        }
        return maxArea;
    }

    /**
     * 方法三：双指针法改进（记录每个基准高度的左右边界）
     * 时间复杂度：O(n)
     * 定义两个长度等于heights的数组用于记录每个基准高度的左右边界。
     * 先遍历每个元素寻找左边界，如果发现元素左边的元素比当前元素要大，则以左边元素的左边界作为新的左边界继续遍历
     * 寻找右边界也重复这样一个过程
     * 最后通过遍历两个记录左右边界的数组找出面积最大的值。
     */
    public int largestRectangleArea3(int[] heights) {

        //定义记录左右边界的两个数组
        int[] lefts = new int[heights.length];
        int[] rights = new int[heights.length];

        //遍历寻找并记录每个基准高度的左边界
        for(int i = 0; i < heights.length; i++){
            int left = i - 1;//从左边一个元素开始寻找左边界
            while(left >= 0 && heights[i] <= heights[left]){
                left = lefts[left];//比基准高度大的高度，以它的左边界作为新的左边界，继续寻找
            }
            lefts[i] = left;//找到左边界之后记录左边界
        }

        //遍历寻找并记录每个基准高度的右边界
        for(int i = heights.length - 1; i >= 0; i--){
            int right = i + 1;//从右边一个元素开始寻找左边界
            while(right < heights.length && heights[i] <= heights[right]){
                right = rights[right];//比基准高度大的高度，以它的右边界作为新的右边界，继续寻找
            }
            rights[i] = right;//找到右边界之后记录右边界
        }

        //求出最大面积
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            int area = (rights[i] - lefts[i] - 1) * heights[i];
            maxArea = area > maxArea ? area : maxArea;
        }

        return maxArea;

    }

    /**
     * 方法四：单调栈
     * 时间复杂度：O(n)
     * 在双指针法的思路上，使用单调栈来跳过不可能成为边界的元素
     */
    public int largestRectangleArea4(int[] heights){
        //定义两个数组用于存放左右边界的指针
        int[] lefts = new int[heights.length];
        int[] rights = new int[heights.length];

        //定义存储可能的边界指针的单调栈
        Deque<Integer> stack = new ArrayDeque<>();

        //遍历找到左边界
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();//一直弹栈，直到找到更小的元素，作为左边界
            }
            lefts[i] = stack.isEmpty() ? -1 : stack.peek();//如果栈被弹空了，左边界就是哨兵指针-1
            stack.push(i);//别忘了将当前元素入栈
        }

        //清空栈准备存右边界
        stack.clear();

        for(int i = heights.length - 1; i >= 0; i--){
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();//一直弹栈，直到找到更小的元素，作为右边界
            }
            rights[i] = stack.isEmpty() ? heights.length : stack.peek();//如果栈被弹空了，右边界就是哨兵指针heights.length
            stack.push(i);
        }

        //ArrayUtils.showArray(Arrays.stream(lefts).boxed().toArray(Integer[]::new));
        //ArrayUtils.showArray(Arrays.stream(rights).boxed().toArray(Integer[]::new));

        //求出最大面积
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            int area = (rights[i] - lefts[i] - 1) * heights[i];
            maxArea = area > maxArea ? area : maxArea;
        }

        return maxArea;
    }

    /**
     * 方法五：单调栈改进（一次遍历同时存入左右边界）
     * 时间复杂度：O(n)
     * 在确定左边界时，若heights[stack.peek()]比当前元素要大，在弹栈之前，就可以确定rights[stack.peek()]等于当前指针
     */
    public int largestRectangleArea5(int[] heights){
        int[] lefts = new int[heights.length];
        int[] rights = new int[heights.length];

        //初始化rights数组，因为这种方法与方法四的区别在于统计右边界时，右边界在数组右端哨兵的元素右边界不会被统计到，所以我们先初始化右边界全部为右端哨兵
        for(int i = 0; i < rights.length; i++) rights[i] = heights.length;

        Deque<Integer> stack = new ArrayDeque<>();

        for(int i = 0; i < rights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                rights[stack.peek()] = i;//在弹栈之前可以记录右边界，因为弹栈的时候对于栈顶指针而言，此时的指针正是其右边第一个比它高度小的元素的指针。
                stack.pop();
            }
            lefts[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        //求出最大面积
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            int area = (rights[i] - lefts[i] - 1) * heights[i];
            maxArea = area > maxArea ? area : maxArea;
        }

        return maxArea;
    }

    //官方题解
    //方法一：单调栈
    public int largestRectangleAreaOfficial1(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

    //方法二：单调栈 + 常数优化
    public int largestRectangleAreaOfficial2(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);//这个方法可以给数组填充元素，底层就是遍历填充

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

}

/**
 * 总结：
 * 1.善于在理解题意，或是理清思路之后，发现特殊数据结构对于解题的帮助，善于借助特殊数据结构缩小时间复杂度。
 * 2.可以先通过暴力枚举解题，再想想哪里可以降低时间复杂度，哪里可以在遍历时避免一些重复的步骤。
 */
